// https://leetcode.cn/problems/delete-operation-for-two-strings/submissions/562952887/

class Solution {
public:
    int minDistance(string s1, string s2) {
        int n = s1.size(), m = s2.size();
        s1.insert(begin(s1), ' '), s2.insert(begin(s2), ' ');
        vector<vector<int>> dp(n+1, vector<int>(m+1, 0));

        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                dp[i][j] = (s1[i] == s2[j]) ? (dp[i-1][j-1]+1) : max(dp[i-1][j], dp[i][j-1]);
        return (n-dp[n][m])+(m-dp[n][m]);
    }
};
